package com.entryLevel;

public class MinCostClimbingStairs0109_746 {
    public int minCostClimbingStairs(int[] cost) {
        /**
         * dp五部曲
         * dp[i] 下标及其含义
         * 初始化
         * 递归公式
         * 递归顺序
         * debug打印数组
         */

        int[] dp = new int[cost.length+1]; //表示 跳到第i个台阶的最少花费。
        dp[0] = 0; dp[1] = 0; // 初始化 题目中表示 可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯

        for (int i = 2; i < cost.length+1; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]); // 递归公式，爬一个或者两个台阶
        }
        return dp[dp.length-1];
    }
}
